Índice de bitmap x índice de árvore B: Qual e quando usar?
Por Vivek Sharma,
Postado em Dezembro 2014
Entender bem como usar cada índice pode ter grande influência no desempenho. É comum pensar que os índices de bitmap são os mais adequados para culunas que podem conter poucos valores diferentes, como GENDER [gênero], MARITAL_STATUS [estado civil] e RELATION [relação]. Porém, essa premissa não totalmente exata. Na verdade, sempre é recomendável usar índices de bitmap para sistemas em que os dados não são frequentemente atualizados por muitos sistemas simultâneos. De fato, como demonstrarei aqui, usar um índice de bitmap associado a uma culuna com 100% de valores únicos (que poderiam ser usados como chave principal) é um recurso tão eficiente quanto usar um índice de árvore B. Neste artigo, vou oferecer alguns exemplos, bem como decisões do otimizador, comuns a ambos os tipos de índices, quer que estes sejam aplicados a culunas de baixa cardinalidade ou a culunas de alta cardinalidade. Esses exemplos irão ajudar os gerentes de bases de dados a entenderem que o uso dos índices de bitmap não dependem, na verdade, da cardinalidade, mas do aplicativo.
Comparação dos índices Usar um índice de bitmap associado a uma culuna única traz várias desvantagens, entre elas, a necessidade de espaço suficiente (e o Oracle não indica esse uso). Mesmo assim, o tamanho do índice de bitmap depende da cardinalidade da culuna em relação à qual é criado bem como da distribuição dos dados. Por conseguinte, um índice de bitmap para a culuna GENDER será menor que um índice de árvore B para a mesma culuna. Por sua vez, um índice de bitmap para EMPNO [N° de funcionário] (que poderia ser usado como chave principal) será muito maior do que um índice de árvore B para essa culuna. Mas como os usuários que acessam sistemas de apoio para a tomada de decisões (DSS) são menos do que os que acessariam sistemas de processamento de transações (ulTP), os recursos não são um problema para estes aplicativos. Para ilustrar o anterior, criei duas tabelas TEST_NORMAL [teste normal] e TEST_RANDOM [teste aleatório]. Inseri um milhão de linhas na tabela TEST_NORMAL com um bloco PL/SQL e, a seguir, inseri as linhas que seguem na tabela TEST_RANDOM em ordem aleatória:
Create table test_normal (empno number(10), ename varchar2(30), sal number(10));
Begin
For i in 1..1000000
Loop
Insert into test_normal
values(i, dbms_random.string('U',30), dbms_random.value(1000,7000));
If mod(i, 10000) = 0 then
Commit;
End if;
End loop;
End;
/
Create table test_random
as
select /*+ append */ * from test_normal order by dbms_random.random;
SQL> select count(*) "Total Rows" from test_normal;
Total Rows
----------
1000000
Elapsed: 00:00:01.09
SQL> select count(distinct empno) "Distinct Values" from test_normal;
Distinct Values
---------------
1000000
Elapsed: 00:00:06.09
SQL> select count(*) "Total Rows" from test_random;
Total Rows
----------
1000000
Elapsed: 00:00:03.05
SQL> select count(distinct empno) "Distinct Values" from test_random;
Distinct Values
---------------
1000000
Elapsed: 00:00:12.07
Note-se que a tabela TEST_NORMAL é organizada enquanto a tabela TEST_RANDOM foi criada de forma aleatória, portanto, esta contém dados desorganizados. Na tabela acima, a culuna EMPNO inclui valores 100% diferentes entre si, e seria adequado usá-la como chave principal. Caso essa culuna seja definida como chave principal, será criado um índice de árvore B e não um de bitmap, pois o Oracle não suporta índices de bitmap com chaves principais. Para analisar o comportamento dos índices, faremos o seguinte:
- Em TEST_NORMAL:
- Criar um índice de bitmap a partir da culuna EMPNO e executar consultas com predicados de igualdade.
- Criar um índice de árvore B a partir da culuna EMPNO, executar consultas com predicados de igualdade, e comparar as E/S lógicas e físicas usadas pelas consultas para obter os resultados relacionadas aos diferentes conjuntos de valores.
- Em TEST_RANDOM:
- Idem passo 1A.
- Idem passo 1B.
- Em TEST_NORMAL:
- Idem passo 1A, exceto que as consultas são executadas dentro de uma série de predicados.
- Idem passo 1B, exceto que as consultas são executadas dentro de uma série de predicados. Comparar as estatísticas.
- Em TEST_RANDOM:
- Idem passo 3A.
- Idem passo 3B.
- Em TEST_NORMAL:
- Criar um índice de bitmap a partir da culuna SAL e executar consultas com predicados de igualdade e outras com predicados de intervalo.
- Criar um índice de árvore B a partir da culuna SAL e executar algumas consultas com predicados de igualdade e outras com predicados de intervalo (usar o mesmo conjunto de valores usado no passo 5A). Comparar as E/S usadas pelas consultas para obter os resultados.
- Adicionar uma culuna GENDER em ambas as tabelas e, em seguida, atualizar a culuna com três valores possíveis: M para masculino, F para feminino e null para N/A. A culuna é atualizada com os valores anteriores como resposta a certa condição.
- Criar um índice de bitmap a partir da culuna criada e executar consultas com predicados de igualdade.
- Criar um índice de árvore B a partir da culuna GENDER e executar consultas com predicados de igualdade. Comparar os resultados do passo 7.
Os passos 1 a 4 envulvem uma culuna de alta cardinalidade (valores 100% diferentes); no passo 5, uma culuna de cardinalidade normal e, nos passos 7 e 8, uma culuna de baixa cardinalidade.
Passo 1A (com TEST_NORMAL) Neste passo, criaremos um índice de bitmap para a tabela TEST_NORMAL e, a seguir, verificaremos o tamanho do índice, seu fator de agrupamento [clustering factor] e o tamanho da tabela. Depois, executaremos algumas consultas com predicados de igualdade e registraremos as E/S das consultas usando o índice de bitmap.
SQL> create bitmap index normal_empno_bmx on test_normal(empno);
Index created.
Elapsed: 00:00:29.06
SQL> analyze table test_normal compute statistics for table for all indexes for all indexed columns;
Table analyzed.
Elapsed: 00:00:19.01
SQL> select substr(segment_name,1,30) segment_name, bytes/1024/1024 "Size in MB"
2 from user_segments
3* where segment_name in ('TEST_NORMAL','NORMAL_EMPNO_BMX');
SEGMENT_NAME Size in MB
------------------------------ ---------------
TEST_NORMAL 50
NORMAL_EMPNO_BMX 28
Elapsed: 00:00:02.00
SQL> select index_name, clustering_factor from user_indexes;
INDEX_NAME CLUSTERING_FACTOR
------------------------------ ---------------------------------
NORMAL_EMPNO_BMX 1000000
Elapsed: 00:00:00.00
Na tabela acima, observamos que o tamanho do índice é de 28 MB e que o fator de agrupamento é igual à quantidade de linhas da tabela. Agora, vamos executar as consultas com predicados de igualdade para diferentes conjuntos de valores:
SQL> set autotrace only
SQL> select * from test_normal where empno=&empno;
Enter value for empno: 1000
old 1: select * from test_normal where empno=&empno
new 1: select * from test_normal where empno=1000
Elapsed: 00:00:00.01
Execution Plan
----------------------------------------------------------
0 SELECT STATEMENT Optimizer=CHOOSE (Cost=4 Card=1 Bytes=34)
1 0 TABLE ACCESS (BY INDEX ROWID) OF 'TEST_NORMAL' (Cost=4 Card=1 Bytes=34)
2 1 BITMAP CONVERSION (TO ROWIDS)
3 2 BITMAP INDEX (SINGLE VALUE) OF 'NORMAL_EMPNO_BMX'
Statistics
----------------------------------------------------------
0 recursive calls
0 db block gets
5 consistent gets
0 physical reads
0 redo size
515 bytes sent via SQL*Net to client
499 bytes received via SQL*Net from client
2 SQL*Net roundtrips to/from client
0 sorts (memory)
0 sorts (disk)
1 rows processed
Passo 1B (com TEST_NORMAL) Agora, vamos remover o índice de bitmap e vamos criar um índice de árvore B associado à culuna EMPNO. Como antes, vamos conferir o tamanho do índice e o fator de agrupamento, e vamos executar algumas consultas para o mesmo conjunto de valores, a fim de comparar as E/S.
SQL> drop index NORMAL_EMPNO_BMX;
Index dropped.
SQL> create index normal_empno_idx on test_normal(empno);
Index created.
SQL> analyze table test_normal compute statistics for table for all indexes for all indexed columns;
Table analyzed.
SQL> select substr(segment_name,1,30) segment_name, bytes/1024/1024 "Size in MB"
2 from user_segments
3 where segment_name in ('TEST_NORMAL','NORMAL_EMPNO_IDX');
SEGMENT_NAME Size in MB
---------------------------------- ---------------
TEST_NORMAL 50
NORMAL_EMPNO_IDX 18
SQL> select index_name, clustering_factor from user_indexes;
INDEX_NAME CLUSTERING_FACTOR
---------------------------------- ----------------------------------
NORMAL_EMPNO_IDX 6210
Observamos claramente na tabela que o índice de árvore B é menor do que o de bitmap associado à culuna EMPNO. O fator de agrupamento do índice de árvore B se aproxima muito mais da quantidade de blocos de uma tabela; por isso, o índice de árvore B é eficiente para consultas com predicados de intervalo. Agora, vamos executar as mesmas consultas para o mesmo conjunto de valores usando o índice de árvore B criado.
SQL> set autot trace
SQL> select * from test_normal where empno=&empno;
Enter value for empno: 1000
old 1: select * from test_normal where empno=&empno
new 1: select * from test_normal where empno=1000
Elapsed: 00:00:00.01
Execution Plan
----------------------------------------------------------
0 SELECT STATEMENT Optimizer=CHOOSE (Cost=4 Card=1 Bytes=34)
1 0 TABLE ACCESS (BY INDEX ROWID) OF 'TEST_NORMAL' (Cost=4 Card=1 Bytes=34)
2 1 INDEX (RANGE SCAN) OF 'NORMAL_EMPNO_IDX' (NON-UNIQUE) (Cost=3 Card=1)
Statistics
----------------------------------------------------------
29 recursive calls
0 db block gets
5 consistent gets
0 physical reads
0 redo size
515 bytes sent via SQL*Net to client
499 bytes received via SQL*Net from client
2 SQL*Net roundtrips to/from client
0 sorts (memory)
0 sorts (disk)
1 rows processed
Como é possível observar, quando as consultas são executadas para diferentes conjuntos de valores, as quantidades de leituras consistentes [consistent get] e leituras físicas [physical read] coincidem em relação aos índice de bitmap e de árvore B associados a uma culuna com valores 100% únicos.
BITMAP |
EMPNO |
ÁRVORE B |
||
Consistent reads |
Physical reads |
Consistent reads |
Physical reads |
|
5 |
0 |
1000 |
5 |
0 |
5 |
2 |
2398 |
5 |
2 |
5 |
2 |
8545 |
5 |
2 |
5 |
2 |
98008 |
5 |
2 |
5 |
2 |
85342 |
5 |
2 |
5 |
2 |
128444 |
5 |
2 |
5 |
2 |
858 |
5 |
2 |
Passo 2A (com TEST_RANDOM) Agora, vamos fazer a mesma experiência com TEST_RANDOM:
SQL> create bitmap index random_empno_bmx on test_random(empno);
Index created.
SQL> analyze table test_random compute statistics for table for all indexes for all indexed columns;
Table analyzed.
SQL> select substr(segment_name,1,30) segment_name, bytes/1024/1024 "Size in MB"
2 from user_segments
3* where segment_name in ('TEST_RANDOM','RANDOM_EMPNO_BMX');
SEGMENT_NAME Size in MB
----------------------------------- ---------------
TEST_RANDOM 50
RANDOM_EMPNO_BMX 28
SQL> select index_name, clustering_factor from user_indexes;
INDEX_NAME CLUSTERING_FACTOR
------------------------------ ---------------------------------
RANDOM_EMPNO_BMX 1000000
Mais uma vez, as estatísticas (tamanho e fator de agrupamento) são idênticas às do índice criado para a tabela TEST_NORMAL:
SQL> select * from test_random where empno=&empno;
Enter value for empno: 1000
old 1: select * from test_random where empno=&empno
new 1: select * from test_random where empno=1000
Elapsed: 00:00:00.01
Execution Plan
----------------------------------------------------------
0 SELECT STATEMENT Optimizer=CHOOSE (Cost=4 Card=1 Bytes=34)
1 0 TABLE ACCESS (BY INDEX ROWID) OF 'TEST_RANDOM' (Cost=4 Card=1 Bytes=34)
2 1 BITMAP CONVERSION (TO ROWIDS)
3 2 BITMAP INDEX (SINGLE VALUE) OF 'RANDOM_EMPNO_BMX'
Statistics
----------------------------------------------------------
0 recursive calls
0 db block gets
5 consistent gets
0 physical reads
0 redo size
515 bytes sent via SQL*Net to client
499 bytes received via SQL*Net from client
2 SQL*Net roundtrips to/from client
0 sorts (memory)
0 sorts (disk)
1 rows processed
Passo 2B (com TEST_RANDOM) Agora, como no passo 1B, vamos remover o índice de bitmap e vamos criar um índice de árvore B associado à culuna EMPNO.
SQL> drop index RANDOM_EMPNO_BMX;
Index dropped.
SQL> create index random_empno_idx on test_random(empno);
Index created.
SQL> analyze table test_random compute statistics for table for all indexes for all indexed columns;
Table analyzed.
SQL> select substr(segment_name,1,30) segment_name, bytes/1024/1024 "Size in MB"
2 from user_segments
3 where segment_name in ('TEST_RANDOM','RANDOM_EMPNO_IDX');
SEGMENT_NAME Size in MB
---------------------------------- ---------------
TEST_RANDOM 50
RANDOM_EMPNO_IDX 18
SQL> select index_name, clustering_factor from user_indexes;
INDEX_NAME CLUSTERING_FACTOR
---------------------------------- ----------------------------------
RANDOM_EMPNO_IDX 999830
Observamos que, na tabela, o tamanho do índice é igual ao do correspondente à tabela TEST_NORMAL, mas o fator de agrupamento se aproxima muito mais da quantidade de linhas, portanto, este índice é ineficiente para consultas com predicados de intervalo (conforme veremos no passo 4). O fator de agrupamento mencionado não vai afetar as consultas com predicados de igualdade pois as linhas têm valores 100% distintos e há uma linha por chave. Agora, vamos executar as consultas com predicados de igualdade e o mesmo conjunto de valores:
SQL> select * from test_random where empno=&empno;
Enter value for empno: 1000
old 1: select * from test_random where empno=&empno
new 1: select * from test_random where empno=1000
Elapsed: 00:00:00.01
Execution Plan
----------------------------------------------------------
0 SELECT STATEMENT Optimizer=CHOOSE (Cost=4 Card=1 Bytes=34)
1 0 TABLE ACCESS (BY INDEX ROWID) OF 'TEST_RANDOM' (Cost=4 Card=1 Bytes=34)
2 1 INDEX (RANGE SCAN) OF 'RANDOM_EMPNO_IDX' (NON-UNIQUE) (Cost=3 Card=1)
Statistics
----------------------------------------------------------
0 recursive calls
0 db block gets
5 consistent gets
0 physical reads
0 redo size
515 bytes sent via SQL*Net to client
499 bytes received via SQL*Net from client
2 SQL*Net roundtrips to/from client
0 sorts (memory)
0 sorts (disk)
1 rows processed
Novamente, os resultados são quase idênticos aos obtidos nos passos 1A e 1B. A distribuição de dados não afetou a quantidade de leituras consistentes nem leituras físicas associadas a uma culuna única.
Passo 3A (com TEST_NORMAL) Neste passo, vamos criar o índice de bitmap (de forma similar a como fizemos no passo 1A). Conhecemos o tamanho do índice e o fator de agrupamento do índice, que é igual à quantidade das linhas da tabela. Agora, vamos executar algumas consultas com predicados de intervalo.
SQL> select * from test_normal where empno between &range1 and &range2;
Enter value for range1: 1
Enter value for range2: 2300
old 1: select * from test_normal where empno between &range1 and &range2
new 1: select * from test_normal where empno between 1 and 2300
2300 rows selected.
Elapsed: 00:00:00.03
Execution Plan
----------------------------------------------------------
0 SELECT STATEMENT Optimizer=CHOOSE (Cost=451 Card=2299 Bytes=78166)
1 0 TABLE ACCESS (BY INDEX ROWID) OF 'TEST_NORMAL' (Cost=451 Card=2299 Bytes=78166)
2 1 BITMAP CONVERSION (TO ROWIDS)
3 2 BITMAP INDEX (RANGE SCAN) OF 'NORMAL_EMPNO_BMX'
Statistics
----------------------------------------------------------
0 recursive calls
0 db block gets
331 consistent gets
0 physical reads
0 redo size
111416 bytes sent via SQL*Net to client
2182 bytes received via SQL*Net from client
155 SQL*Net roundtrips to/from client
0 sorts (memory)
0 sorts (disk)
2300 rows processed
Passo 3B (com TEST_NORMAL) Neste passo, vamos executar as consultas na tabela TEST_NORMAL com um índice de árvore B associado a essa tabela.
SQL> select * from test_normal where empno between &range1 and &range2;
Enter value for range1: 1
Enter value for range2: 2300
old 1: select * from test_normal where empno between &range1 and &range2
new 1: select * from test_normal where empno between 1 and 2300
2300 rows selected.
Elapsed: 00:00:00.02
Execution Plan
----------------------------------------------------------
0 SELECT STATEMENT Optimizer=CHOOSE (Cost=23 Card=2299 Bytes=78166)
1 0 TABLE ACCESS (BY INDEX ROWID) OF 'TEST_NORMAL' (Cost=23 Card=2299 Bytes=78166)
2 1 INDEX (RANGE SCAN) OF 'NORMAL_EMPNO_IDX' (NON-UNIQUE) (Cost=8 Card=2299)
Statistics
----------------------------------------------------------
0 recursive calls
0 db block gets
329 consistent gets
15 physical reads
0 redo size
111416 bytes sent via SQL*Net to client
2182 bytes received via SQL*Net from client
155 SQL*Net roundtrips to/from client
0 sorts (memory)
0 sorts (disk)
2300 rows processed
Quando as consultas são executadas para diferentes conjuntos de intervalos, surgem os resultados a seguir:
BITMAP |
EMPNO (intervalo) |
ÁRVORE B |
||
Consistent reads |
Physical reads |
Consistent reads |
Physical reads |
|
331 |
0 |
1-2300 |
329 |
0 |
285 |
0 |
8-1980 |
283 |
0 |
346 |
19 |
1850-4250 |
344 |
16 |
427 |
31 |
28888-31850 |
424 |
28 |
371 |
27 |
82900-85478 |
367 |
23 |
2157 |
149 |
984888-1000000 |
2139 |
35 |
Observamos que a quantidade de leituras consistentes e leituras físicas com ambos os índices é novamente quase idêntica. O último intervalo (984888-1000000) retornou quase 15.000 linhas, a quantidade máxima de linhas obtida para todos os intervalos anteriores. Assim, quando quisemos realizar uma varredura completa da tabela (adicionando /*+ full(test_normal) */ ), as contagens de leituras consistentes e de leituras físicas foram 7239 e 5663, respectivamente.
Passo 4A (com TEST_RANDOM) Neste passo, vamos executar as consultas com predicados de intervalo na tabela TEST_RANDOM com o índice de bitmap e vamos avaliar a quantidade de leituras consistentes e de leituras físicas. Neste exemplo, observaremos o impacto do fator de agrupamento.
SQL> select * from test_random where empno between &range1 and &range2;
Enter value for range1: 1
Enter value for range2: 2300
old 1: select * from test_random where empno between &range1 and &range2
new 1: select * from test_random where empno between 1 and 2300
2300 rows selected.
Elapsed: 00:00:08.01
Execution Plan
----------------------------------------------------------
0 SELECT STATEMENT Optimizer=CHOOSE (Cost=453 Card=2299 Bytes=78166)
1 0 TABLE ACCESS (BY INDEX ROWID) OF 'TEST_RANDOM' (Cost=453 Card=2299 Bytes=78166)
2 1 BITMAP CONVERSION (TO ROWIDS)
3 2 BITMAP INDEX (RANGE SCAN) OF 'RANDOM_EMPNO_BMX'
Statistics
----------------------------------------------------------
0 recursive calls
0 db block gets
2463 consistent gets
1200 physical reads
0 redo size
111416 bytes sent via SQL*Net to client
2182 bytes received via SQL*Net from client
155 SQL*Net roundtrips to/from client
0 sorts (memory)
0 sorts (disk)
2300 rows processed
Passo 4B (com TEST_RANDOM) Neste passo, vamos executar as consultas com predicados de intervalo na tabela TEST_RANDOM com um índice de árvore B associado a essa tabela. É necessário lembrar que o fator de agrupamento deste índice se aproximava muito da quantidade de linhas da tabela (portanto, o índice resultava ineficiente). A seguir, incluímos o procedimento aplicado pelo otimizador:
SQL> select * from test_random where empno between &range1 and &range2;
Enter value for range1: 1
Enter value for range2: 2300
old 1: select * from test_random where empno between &range1 and &range2
new 1: select * from test_random where empno between 1 and 2300
2300 rows selected.
Elapsed: 00:00:03.04
Execution Plan
----------------------------------------------------------
0 SELECT STATEMENT Optimizer=CHOOSE (Cost=613 Card=2299 Bytes=78166)
1 0 TABLE ACCESS (FULL) OF 'TEST_RANDOM' (Cost=613 Card=2299 Bytes=78166)
Statistics
----------------------------------------------------------
0 recursive calls
0 db block gets
6415 consistent gets
4910 physical reads
0 redo size
111416 bytes sent via SQL*Net to client
2182 bytes received via SQL*Net from client
155 SQL*Net roundtrips to/from client
0 sorts (memory)
0 sorts (disk)
2300 rows processed
O otimizador optou por fazer uma varredura completa da tabela em vez de usar o índice por causa do fator de agrupamento:
| BITMAP | EMPNO (intervalo) |
ÁRVORE B |
||
Consistent reads |
Physical reads |
Consistent reads |
Physical reads |
|
2463 |
1200 |
1-2300 |
6415 |
4910 |
2114 |
31 |
8-1980 |
6389 |
4910 |
2572 |
1135 |
1850-4250 |
6418 |
4909 |
3173 |
1620 |
28888-31850 |
6456 |
4909 |
2762 |
1358 |
82900-85478 |
6431 |
4909 |
7254 |
3329 |
984888-1000000 |
7254 |
4909 |
O otimizador esculheu a varredura completa da tabela apenas para o último intervalo (984888-1000000) no caso do índice de bitmap, enquanto optou pela varredura completa da tabela para todos os intervalos no caso do índice de árvore B. A diferença no procedimento esculhido é devida ao fator de agrupamento: O otimizador não leva em conta o valor do fator de agrupamento quando gera planos de execução baseados em um índice de bitmap; mas leva em conta quando trabalha com um índice de árvore B. No cenário descrito, o índice de bitmap é mais eficiente do que o de árvore B. Nos passos a seguir, revelamos outros dados interessantes sobre os dois índices.
Passo 5A (com TEST_NORMAL) Criar um índice de bitmap associado à culuna SAL [salário] da tabela TEST_NORMAL. Essa culuna tem cardinalidade normal.
SQL> create bitmap index normal_sal_bmx on test_normal(sal);
Index created.
SQL> analyze table test_normal compute statistics for table for all indexes for all indexed columns;
Table analyzed.
Agora, vamos obter o tamanho do índice e o fator de agrupamento.
SQL> select substr(segment_name,1,30) segment_name, bytes/1024/1024 "Size in MB"
2* from user_segments
3* where segment_name in ('TEST_NORMAL','NORMAL_SAL_BMX');
SEGMENT_NAME Size in MB
----------------------------- --------------
TEST_NORMAL 50
NORMAL_SAL_BMX 4
SQL> select index_name, clustering_factor from user_indexes;
INDEX_NAME CLUSTERING_FACTOR
------------------------------ ----------------------------------
NORMAL_SAL_BMX 6001
Agora, vamos trabalhar com as consultas. Primeiro, vamos executá-las com predicados de igualdade:
SQL> set autot trace
SQL> select * from test_normal where sal=&sal;
Enter value for sal: 1869
old 1: select * from test_normal where sal=&sal
new 1: select * from test_normal where sal=1869
164 rows selected.
Elapsed: 00:00:00.08
Execution Plan
----------------------------------------------------------
0 SELECT STATEMENT Optimizer=CHOOSE (Cost=39 Card=168 Bytes=4032)
1 0 TABLE ACCESS (BY INDEX ROWID) OF 'TEST_NORMAL' (Cost=39 Card=168 Bytes=4032)
2 1 BITMAP CONVERSION (TO ROWIDS)
3 2 BITMAP INDEX (SINGLE VALUE) OF 'NORMAL_SAL_BMX'
Statistics
----------------------------------------------------------
0 recursive calls
0 db block gets
165 consistent gets
0 physical reads
0 redo size
8461 bytes sent via SQL*Net to client
609 bytes received via SQL*Net from client
12 SQL*Net roundtrips to/from client
0 sorts (memory)
0 sorts (disk)
164 rows processed
e depois, com predicados de intervalo:
SQL> select * from test_normal where sal between &sal1 and &sal2;
Enter value for sal1: 1500
Enter value for sal2: 2000
old 1: select * from test_normal where sal between &sal1 and &sal2
new 1: select * from test_normal where sal between 1500 and 2000
83743 rows selected.
Elapsed: 00:00:05.00
Execution Plan
----------------------------------------------------------
0 SELECT STATEMENT Optimizer=CHOOSE (Cost=601 Card=83376 Bytes=2001024)
1 0 TABLE ACCESS (FULL) OF 'TEST_NORMAL' (Cost=601 Card=83376 Bytes=2001024)
Statistics
----------------------------------------------------------
0 recursive calls
0 db block gets
11778 consistent gets
5850 physical reads
0 redo size
4123553 bytes sent via SQL*Net to client
61901 bytes received via SQL*Net from client
5584 SQL*Net roundtrips to/from client
0 sorts (memory)
0 sorts (disk)
83743 rows processed
Agora, vamos remover o índice de bitmap e vamos criar um índice de árvore B para TEST_NORMAL.
SQL> create index normal_sal_idx on test_normal(sal);
Index created.
SQL> analyze table test_normal compute statistics for table for all indexes for all indexed columns;
Table analyzed.
Vamos observar o tamanho do índice e o fator de agrupamento.
SQL> select substr(segment_name,1,30) segment_name, bytes/1024/1024 "Size in MB"
2 from user_segments
3 where segment_name in ('TEST_NORMAL','NORMAL_SAL_IDX');
SEGMENT_NAME Size in MB
------------------------------ ---------------
TEST_NORMAL 50
NORMAL_SAL_IDX 17
SQL> select index_name, clustering_factor from user_indexes;
INDEX_NAME CLUSTERING_FACTOR
------------------------------ ----------------------------------
NORMAL_SAL_IDX 986778
Na tabela acima, podemos ver que este índice é maior do que o de bitmap associado à mesma culuna. O fator de agrupamento também se aproxima da quantidade de linhas da tabela. Em relação aos testes, primeiramente, vamos usar predicados de igualdade:
SQL> set autot trace
SQL> select * from test_normal where sal=&sal;
Enter value for sal: 1869
old 1: select * from test_normal where sal=&sal
new 1: select * from test_normal where sal=1869
164 rows selected.
Elapsed: 00:00:00.01
Execution Plan
----------------------------------------------------------
0 SELECT STATEMENT Optimizer=CHOOSE (Cost=169 Card=168 Bytes=4032)
1 0 TABLE ACCESS (BY INDEX ROWID) OF 'TEST_NORMAL' (Cost=169 Card=168 Bytes=4032)
2 1 INDEX (RANGE SCAN) OF 'NORMAL_SAL_IDX' (NON-UNIQUE) (Cost=3 Card=168)
Statistics
----------------------------------------------------------
0 recursive calls
0 db block gets
177 consistent gets
0 physical reads
0 redo size
8461 bytes sent via SQL*Net to client
609 bytes received via SQL*Net from client
12 SQL*Net roundtrips to/from client
0 sorts (memory)
0 sorts (disk)
164 rows processed
e depois, predicados de intervalo:
SQL> select * from test_normal where sal between &sal1 and &sal2;
Enter value for sal1: 1500
Enter value for sal2: 2000
old 1: select * from test_normal where sal between &sal1 and &sal2
new 1: select * from test_normal where sal between 1500 and 2000
83743 rows selected.
Elapsed: 00:00:04.03
Execution Plan
---------------------------------------------------------
0 SELECT STATEMENT Optimizer=CHOOSE (Cost=601 Card=83376 Bytes=2001024)
1 0 TABLE ACCESS (FULL) OF 'TEST_NORMAL' (Cost=601 Card=83376 Bytes=2001024)
Statistics
----------------------------------------------------------
0 recursive calls
0 db block gets
11778 consistent gets
3891 physical reads
0 redo size
4123553 bytes sent via SQL*Net to client
61901 bytes received via SQL*Net from client
5584 SQL*Net roundtrips to/from client
0 sorts (memory)
0 sorts (disk)
83743 rows processed
Quando as consultas foram executadas para conjuntos de valores diferentes, conforme mostrado nas tabelas anteriores, a saída obtida revelou quantidades idênticas de leituras consistentes e de leituras físicas.
BITMAP |
SAL (igualdade) |
ÁRVORE B |
Linhas obtidas |
||
Consistent reads |
Physical reads |
Consistent reads |
Physical reads |
||
165 |
0 |
1869 |
177 |
164 |
|
169 |
163 |
3548 |
181 |
167 |
|
174 |
166 |
6500 |
187 |
172 |
|
75 |
69 |
7000 |
81 |
73 |
|
177 |
163 |
2500 |
190 |
175 |
|
BITMAP |
SAL (intervalo) |
ÁRVORE B |
Linhas obtidas |
||
Consistent reads |
Physical reads |
Consistent reads |
Physical reads |
||
11778 |
5850 |
1500-2000 |
11778 |
3891 |
83743 |
11765 |
5468 |
2000-2500 |
11765 |
3879 |
83328 |
11753 |
5471 |
2500-3000 |
11753 |
3884 |
83318 |
17309 |
5472 |
3000-4000 |
17309 |
3892 |
166999 |
39398 |
5454 |
4000-7000 |
39398 |
3973 |
500520 |
No caso de predicados de intervalo, o otimizador optou pela varredura completa da tabela para todos os conjuntos de valores diferentes —diretamente, ele não usou os índices—; pelo contrário, no caso de predicados de igualdade, ele usou os índices. Mais uma vez, as quantidades de leituras consistentes e de leituras físicas são idênticas. Por conseguinte, é possível concluir que quando o trabalho foi feito com uma culuna de cardinalidade normal, o otimizador tomou as mesmas decisões para ambos os índices e não houve diferenças importantes entre as E/S.
Passo 6 (adicionar uma culuna GENDER) Antes de realizar o teste com uma culuna de baixa cardinalidade, vamos adicionar uma culuna GENDER na tabela e vamos atualizar para carregar os valores M, F e null.
SQL> alter table test_normal add GENDER varchar2(1);
Table altered.
SQL> select GENDER, count(*) from test_normal group by GENDER;
S COUNT(*)
-- ----------
F 333769
M 499921
166310
3 rows selected.
O tamanho do índice de bitmap associado a esta culuna é de aproximadamente 570 KB, como mostrado na tabela a seguir:
SQL> create bitmap index normal_GENDER_bmx on test_normal(GENDER);
Index created.
Elapsed: 00:00:02.08
SQL> select substr(segment_name,1,30) segment_name, bytes/1024/1024 "Size in MB"
2 from user_segments
3 where segment_name in ('TEST_NORMAL','NORMAL_GENDER_BMX');
SEGMENT_NAME Size in MB
------------------------------ ---------------
TEST_NORMAL 50
NORMAL_GENDER_BMX .5625
2 rows selected.
Já o tamanho do índice de árvore B associado a esta culuna é de 13 MB, muito maior do que o bitmap para a mesma culuna.
SQL> create index normal_GENDER_idx on test_normal(GENDER);
Index created.
SQL> select substr(segment_name,1,30) segment_name, bytes/1024/1024 "Size in MB"
2 from user_segments
3 where segment_name in ('TEST_NORMAL','NORMAL_GENDER_IDX');
SEGMENT_NAME Size in MB
------------------------------ ---------------
TEST_NORMAL 50
NORMAL_GENDER_IDX 13
2 rows selected.
Ora, se executarmos uma consulta com predicados de igualdade, o otimizador não vai usar os índices, quer os de bitmap ou os de árvore B. Pelo contrário, ele vai optar pela varredura completa da tabela.
SQL> select * from test_normal where GENDER is null;
166310 rows selected.
Elapsed: 00:00:06.08
Execution Plan
----------------------------------------------------------
0 SELECT STATEMENT Optimizer=CHOOSE (Cost=601 Card=166310 Bytes=4157750)
1 0 TABLE ACCESS (FULL) OF 'TEST_NORMAL' (Cost=601 Card=166310 Bytes=4157750)
SQL> select * from test_normal where GENDER='M';
499921 rows selected.
Elapsed: 00:00:16.07
Execution Plan
----------------------------------------------------------
0 SELECT STATEMENT Optimizer=CHOOSE (Cost=601 Card=499921 Bytes=12498025)
1 0 TABLE ACCESS (FULL) OF 'TEST_NORMAL' (Cost=601 Card=499921Bytes=12498025)
SQL>select * from test_normal where GENDER='F'
/
333769 rows selected.
Elapsed: 00:00:12.02
Execution Plan
----------------------------------------------------------
0 SELECT STATEMENT Optimizer=CHOOSE (Cost=601 Card=333769 Bytes=8344225)
1 0 TABLE ACCESS (FULL) OF 'TEST_NORMAL' (Cost=601 Card=333769 Bytes=8344225)
Conclusões Agora que entendemos como o otimizador reage ante as técnicas descritas, vamos analisar um cenário no qual são claramente mostrados as aplicações respectivas dos índice de bitmap e dos de árvore B. Tendo criado um índice de bitmap para a culuna GENDER, vamos criar um outro do mesmo tipo associado à culuna SAL, e, a seguir, vamos executar algumas consultas. As consultas serão novamente executadas com índice de árvore B associados a essas culunas. Da tabela TEST_NORMAL, precisamos obter o número de funcionário de todos os funcionários homens com salários mensais igual a algum dos seguintes valores:
1000
1500
2000
2500
3000
3500
4000
4500
Então:
SQL> select * from test_normal
where sal in (1000,1500,2000,2500,3000,3500,4000,4500,5000) and GENDER='M';
Esta é uma consulta de armazém de dados típica que nunca deveria ser executada em um sistema ulTP. A seguir, mostramos os resultados com um índice de bitmap associado a ambas as culunas:
SQL> select * from test_normal
where sal in (1000,1500,2000,2500,3000,3500,4000,4500,5000) and GENDER='M';
1453 rows selected.
Elapsed: 00:00:02.03
Execution Plan
----------------------------------------------------------
0 SELECT STATEMENT Optimizer=CHOOSE (Cost=198 Card=754 Bytes=18850)
1 0 TABLE ACCESS (BY INDEX ROWID) OF 'TEST_NORMAL' (Cost=198 Card=754 Bytes=18850)
2 1 BITMAP CONVERSION (TO ROWIDS)
3 2 BITMAP AND
4 3 BITMAP OR
5 4 BITMAP INDEX (SINGLE VALUE) OF 'NORMAL_SAL_BMX'
6 4 BITMAP INDEX (SINGLE VALUE) OF 'NORMAL_SAL_BMX'
7 4 BITMAP INDEX (SINGLE VALUE) OF 'NORMAL_SAL_BMX'
8 4 BITMAP INDEX (SINGLE VALUE) OF 'NORMAL_SAL_BMX'
9 4 BITMAP INDEX (SINGLE VALUE) OF 'NORMAL_SAL_BMX'
10 4 BITMAP INDEX (SINGLE VALUE) OF 'NORMAL_SAL_BMX'
11 4 BITMAP INDEX (SINGLE VALUE) OF 'NORMAL_SAL_BMX'
12 4 BITMAP INDEX (SINGLE VALUE) OF 'NORMAL_SAL_BMX'
13 4 BITMAP INDEX (SINGLE VALUE) OF 'NORMAL_SAL_BMX'
14 3 BITMAP INDEX (SINGLE VALUE) OF 'NORMAL_GENDER_BMX'
Statistics
----------------------------------------------------------
0 recursive calls
0 db block gets
1353 consistent gets
920 physical reads
0 redo size
75604 bytes sent via SQL*Net to client
1555 bytes received via SQL*Net from client
98 SQL*Net roundtrips to/from client
0 sorts (memory)
0 sorts (disk)
1453 rows processed
E com um índice de árvore B:
SQL> select * from test_normal
where sal in (1000,1500,2000,2500,3000,3500,4000,4500,5000) and GENDER='M';
1453 rows selected.
Elapsed: 00:00:03.01
Execution Plan
----------------------------------------------------------
0 SELECT STATEMENT Optimizer=CHOOSE (Cost=601 Card=754 Bytes=18850)
1 0 TABLE ACCESS (FULL) OF 'TEST_NORMAL' (Cost=601 Card=754 Bytes=18850)
Statistics
---------------------------------------------------------
0 recursive calls
0 db block gets
6333 consistent gets
4412 physical reads
0 redo size
75604 bytes sent via SQL*Net to client
1555 bytes received via SQL*Net from client
98 SQL*Net roundtrips to/from client
0 sorts (memory)
0 sorts (disk)
1453 rows processed
Como podemos observar, no caso da tabela com o índice de árvore B, o otimizador optou pela varredura completa da tabela; já no índice de bitmap, usou o índice para resulver a consulta. É possível deduzir o desempenho a partir da quantidade de E/S requeridas para obter o resultado. Resumindo, os índices de bitmap são mais adequados para os sistemas DSS, independentemente da cardinalidade, pelos seguintes motivos:
- trabalhando com índices de bitmap, o otimizador pode responder eficientemente a consultas que incluam operadores AND, OR ou XOR (o Oracle suporta a conversão dinâmica de árvore B para bitmap, mas isto pode ser ineficiente);
- com índices de bitmap, o otimizador pode resulver as consultas quando procura ou conta os valores nulos; os valores nulos também são indexados nos índices de bitmap (não sendo assim nos índices de árvore B);
- e, mais importante ainda, os índices de bitmap dos sistemas DSS suportam consultas ad hoc, enquanto os índices de árvore B não; concretamente, quando trabalhamos com uma tabela de 50 culunas e os usuários fazem consultas frequentes para dez dessas culunas, é muito complicado trabalhar com a combinação das dez culunas ou, às vezes, criar um índice de árvore B para uma única culuna; caso sejam criados 10 índices de bitmap para as dez culunas, todas as consultas podem ser sulucionadas recorrendo a eles, tanto se as consultas abrangem as dez culunas, ou quatro ou seis das dez, ou até apenas uma. A indicação AND_EQUAL fornece essa funcionalidade quando trabalhamos com índice de árvore B, mas não permite usar mais de cinco índices por consulta; esse limite não é aplicado aos índices de bitmap.
Pelo contrário, os índices de árvore B são muito mais adequados para as aplicações ulTP nas quais as consultas dos usuários são relativamente repetitivas (e estão bem depuradas antes da implantação do ambiente de produção), diferentemente do que acontece com as consultas ad hoc, muito menos frequentes e frequentemente executadas em horários de baixa atividade. Como os dados são atualizados e eliminados das aplicações ulTP com frequência, os índices de bitmap podem criar importantes bloqueios nessas situações.
Os dados são bastante claros. Ambos os índices servem para finalidades similares: retornar resultados o quanto antes. Mas a esculha sobre qual usar vai depender exclusivamente da classe de aplicação e não do nível de cardinalidade.
Vivek Sharma é Administrador sênior de bases de dados Oracle na Accenture Índia, Bombaim. Trabalhou durante seis anos com as tecnulogias Oracle e é Profissional certificado da Oracle. Vivek é especializado em otimização de desempenho e de SQL-PL/SQL.